package KMP;

public class Kmp {

    //优化next数组
    public static int[] getNext(String findStr){
        char[] str = findStr.toCharArray();
        int[] next = new int[str.length];

        next[0] = -1;
        int k = -1;
        int j = 0;
        while ( j < str.length - 1 ){
            if( k == -1 || str[j] == str[k]){
                if(str[j+1]==str[k+1]){
                    next[++j] = next[++k];
                }else {
                    next[++j] = ++k;
                }
            }else {
                k = next[k];
            }
        }
        return next;

    }

    //没优化NEXT数组
    public static int[] getBadNext(String findStr){

        char[] arr = findStr.toCharArray();
        int[] next = new int[arr.length];

        int k = -1;
        int j = 0;
        next[0] = -1;

        while (j<arr.length-1){
            if(k==-1||arr[j]==arr[k]){
                next[++j] = ++k;
            }else {
                k = next[k];
            }
        }
        return next;

    }

    public static int kmp(String mainStr , String findStr){

        //主串指针
        int i = 0;
        //目标串指针
        int j = 0;

        char[] mainStrs = mainStr.toCharArray();
        char[] findStrs = findStr.toCharArray();

        int[] next = getNext(findStr);

        while (i<mainStrs.length&&j<findStrs.length){
            if(mainStrs[i]==findStrs[j]){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if( j == findStrs.length ){
            return i - j;
        }

        return -1;


    }

    public static void main(String[] args) {
        String mainStr = "abcdfabcde";
        String findStr = "abcde";
        System.out.println(kmp(mainStr,findStr));
    }

}
